home *** CD-ROM | disk | FTP | other *** search
- Path: galaxy.ucr.edu!corsa!datadec
- From: datadec@corsa.ucr.edu (Kevin Marcus)
- Newsgroups: comp.lang.c
- Subject: Re: Finding a prime number
- Date: 18 Feb 1996 11:50:18 GMT
- Organization: UC Riverside, Dept. of Computer Science
- Message-ID: <4g73pq$h7j@galaxy.ucr.edu>
- References: <4fnnfuINNib7@keats.ugrad.cs.ubc.ca> <4fteet$b7e@sun001.spd.dsccc.com> <1996Feb16.180234.114184@kuhub.cc.ukans.edu>
- NNTP-Posting-Host: cs.ucr.edu
-
- In article <1996Feb16.180234.114184@kuhub.cc.ukans.edu>,
- <anh@kuhub.cc.ukans.edu> wrote:
- >
- >prime1*prime2*prim3*...*largest_prime_to_date + 1 ?
- >
- >I have not tried to see how long it would take to multiply a million or
- >whatever the number of primes known is.
-
- Actually, while multiplying them together would certainly take
- awhile, there is probably not enough disk space in the world to
- hold such a number, either.
-
- The largest prime number is certainly a mersenne prime , which was
- something like 2^853000ish - 1. That number alone has roughly
- 300000 digits. Imagine how many mor there are that are smaller than
- it.
-
- Better yet, while it slowly decreases, on average, 10% of the numbers
- from 1 - 10^1000000 are prime. this means there are roughly
- 10^999999 primes. The average length of these primes? Only slightly less
- than 1 million digits. As they say in atari land... Do the math!
-
- BTW, this method of factoring has been known for some time. One
- variation on the above method is using factorials. If it were
- possible to calculate a n factorial for large numbers instantly, and
- there were enough disk space to hold these results (taking the log
- of these numbers is no good since the precision of the log must
- be roughly equivalent to the size of the factorial anyways), then
- factoring could be done quickly using gcd (n, n-1!).
-
- And, one again, unfortunately, it is not possible to use Sterlings
- eqn to produce this number, since even the best enhancements on
- Sterlings don't produce the exact factorial integer for long enough.
-
- Instead, look at a way to represent factorials cheaply, and manipulate
- them simply. You could be a rich person!
-
- --
- Kevin Marcus: http://www.cs.ucr.edu/~datadec
- CS Dept, U/CA, Riverside: mailto:datadec@cs.ucr.edu
- Virus-L archives: ftp://ftp.cs.ucr.edu/pub/virus-l
- OKRA net.citizen Directory Services: http://okra.ucr.edu/okra
-